1. Field of the Invention
The invention generally relates to security and traffic management in enterprise networks. More particularly, aspects of the invention are directed to managing access control lists and traffic flow in computer networks.
2. Description of Related Art
An Access Control List (“ACL”) is a rule-based packet classifier. It plays an essential role in network devices for supporting various services such as firewalls, Virtual Private Networks (“VPNs”) and Quality of Service (“QoS”). ACLs are de facto order-dependent and multi-dimensional. Such properties have many adverse effects. For instance, conflicts may arise that impede security compliance analysis. And these properties make ACLs highly sensitive to change.
ACLs are one of the most important security features in managing access control policies in large scale enterprise networks. An ACL contains a list of entries that define matching criteria inside packet header. Based on first matching rule criteria, each ACL is typically assumed to be a linear list of entries being executed from top down. In conventional operation, the action corresponding to the first entry that matches the condition takes effect. If no match is found, the router then drops the packet (implicit deny). When there are two or more entries matching a given criterion, based on first matching rule, the permit or deny classification of the first matching entry takes effect, whereas subsequent entries become irrelevant (redundant).
The presence of no-effect entries further muddles the ability to comprehend the true semantic meaning of long ACLs, making ACL maintenance extremely difficult. Constant improvement in hardware/software capacity allows routers to handle more traffic flows, giving rise to an increased ACL size. In addition, a fine-granular control for traffic demands for an increased expressiveness of ACL language. This, in turn, further complicates the ability to comprehend the meaning of an ACL in total scope.
FIG. 1 illustrates a computer network 10 including a user computer 12 connected to a network router 14 via the Internet 16. A firewall 18 filters data packets send to or from computers coupled to the router 14. A first set of computers 20a and 20b behind the firewall 18 may be accessed via a first interface 22. And a second set of computers 24a, 24b and 24c may be accessed via a second interface 26.
Depending on ACL information maintained by the firewall 18, traffic flow may be permitted or denied. As shown, traffic may be permitted between the user computer 12 and the computer 24c coupled to second interface 26 as shown by arrow 28. In contrast, traffic from the user computer 12 to the computer 20a may be blocked by the firewall 18, as shown by the dashed arrow 30.
Resembling an if-then statement in the C programming language, the generic syntax of an ACL entry is typically expressed in the form of the if condition then action. The condition may specify source, destination IP address range, protocol and port ranges. The action is binary, either permit or deny. While seemingly straightforward, in practice ACLs can be long, complex and error-prone. Furthermore, there may be hundreds or thousands of ACL entries of ACL entries implemented by multiple routers in a given network.
The complexity of ACLs is reflected in the growing demand for fine granular control of network traffic in the context of network security management and QoS requirements. Due to the order dependency, the intended meaning of every individual ACL entry can be altered or erased with removal of existing entries or addition of new entries. Such an excessive sensitivity to semantics of an ACL due to changes makes it extremely hard to comprehend the meaning of the ACL in total scope.
One area of particular interest is priority-based ACL implementations. In such implementations, each entry in a priority-based ACL will be assigned a priority. The priority value will be used to break a tie if a conflict among entries occurs. Namely, among entries that match an incoming packet, the entry with the highest priority takes effect. A priority-based ACL is a generalization of a commonly-used ACL. It is flexible and adaptive in handling various QoS and security requirements.
Due to the practical significance in a large-scale network security management, the impact of ACLs has been an extensive research topic for many years. One type of method to address the ACL problem is to exploit fruitful theoretical results from the well-known Klee's measure problem. This is a computational geometry problem that is concerned with the efficiency of computing the measure of a union of multidimensional rectangular ranges. Klee provided an algorithm for computing the length of a union of intervals in one dimensional space and showed that time complexity of this algorithm is O(n log n).
It was subsequently shown by Fredman and Weide that Ω(n log n) is optimal in the linear decision tree model. Bentley considered the natural extension to d-dimensional cases, and showed that O(n log n) is also optimal for two dimensions (i.e., d=2). For d>2, the complexity generalizes to an upper bound of O(nd-1 log n). Overmars & Yap exploited the notion of trellis rectangles and used a generalization of the k-d tree to partition the plane into a collection of trellises. They proved that the upper bound of time complexity for computing the Klee's measure of n rectangles in the d-dimensional space is O(nd/2 log n).
Built on theoretical results from Overmars & Yap, Eppstein & Muthukrishnan proposed an algorithm based on the k-d tree for detecting conflicts in two-dimensional priority-based packet filters. A priority-based conflict refers to the presence of two filters with same priority level and different actions on the same packet. The computational complexity of the Eppstein & Muthukrishnan algorithm for determining whether a rule set contains any conflicts is O(n3/2) where n is the size of rule set. This, however, is restricted to two dimensional packet classification and filter conflict detection problems.
Other work relates to routing performance in handling traffic, focusing primarily on designing data structures that support efficient packet classification while minimizing computational resource utilization in dynamic and static environments. For instance, a scheme has been proposed that performs a binary search on a prefix-length structured hash table. Others have given a detailed review of data structures for one-dimensional packet classification in routing tables, focused on longest-prefix matching and most-specific range matching tie breaker data structures.
A refined tie-breaker data structure has been proposed to support two-dimensional packet classification. A memory-efficient B-tree for one-dimensional packet classification has also been proposed. A variant of red-black tree data structures has been proposed for supporting three operations of longest-matching prefix-tables in O(n) where n is the number of (one-dimensional) entries (rules). Another approach only detects conflicts in ACL entries using a framework limited to two dimensional space.
Due to the dimension-induced complexity in ACLs, such approaches are rudimentary solutions and are often ineffective in addressing fundamental issues in ACLs.